/**
 *
 * <p>Assignment Problem.</p>
 *
 * <p>There are m machines assigned to n jobs. The cost of doing each job by each machine is $c_{ij} ≥ 0$. Find the assignment
 * to minimize the cost.</p>
 *
 * <p>The problem can be expressed as linear programming:</p>
 * $$\table
 * \text"Minimize "   , ∑↙{i,j} c_{ij}x_{ij};
 * \text"subject to " , ∑↙i x_{ij} = 1, (1 ≤ i ≤ m);
 *                    , ∑↙j x_{ij} = 1, (1 ≤ j ≤ n);
 *                    , x_{ij} ∈ \{0,1\}
 *                    $$
 *
 * <p>The maximization problem can be transformed into the minimization problem by transforming the cost
 * $c'_{ij} = max\{c_{ij}\} - c_{ij}$</p>
 *
 * <p>The problem is similar to weighted bipartite maximum matching problem.</p>
 *
 * <h2>Hungarian Method</h2>
 * <p>Assuming $m=n$ (the case of $m ≠ n$ will be discussed later). The problem be can expressed as matrix $n × n$.</p>
 * <p>The algorithm is illustrated in a generic form:</p>
 * <ul>
 *     <li>Step 1a: for each row, subtract the minimum value to each of the value.</li>
 *     <li>Step 1b: for each column, subtract the minimum value to each of the value.</li>
 *     <li>Step 2: cross out the minimal number of rows and columns that can cover all 0. If number of lines = n, go to step 4,
 *     else go to step 3.</li>
 *     <li>Step 3: find the minimum entry not crossed out in step 3, add this number to each row/column that is crossed out
 *     (note: add twice for doubly crossed element), then subtract this number to every element. Return to step 3.</li>
 *     <li>Step 4: find the solution.</li>
 * </ul>
 *
 * <pre style="overflow:auto">
 *                                                                                         -2                                                 +1
 *                                                                                          ↓                                                  ↓
 *    ┌────────────────────┐            ┌────────────────────┐            ┌────────────────────┐            ┌──┬─────────────────┐          ┌──┬─────────────────┐           ┌──┬──────────────┬──┐            ┌────────────────────┐
 *    │ 14    5    8    7  │            │  9    0    3    2  │← -5        │  9    0    3    0  │            ├─╴9╶──╴0╶──╴3╶──╴0╶─┤      +1 →├╴10╶──╴0╶──╴3╶──╴0╶─┤← -1       ├╴10╶──╴0╶──╴3╶──╴0╶─┤            │ 10    0*   3    0  │
 *    │                    │            │                    │            │                    │            │  │                 │          │  │                 │           │  │              │  │            │                    │
 *    │  2   12    6    5  │            │  0   10    4    3  │← -2        │  0   10    4    1  │            │  0   10    4    1  │          │  0    9    3  [ 0 ]│← -1       │  0    9    3    0  │            │  0    9    3    0* │
 *    │                    │            │                    │            │                    │            │  │                 │          │  │                 │           │  │              │  │            │                    │
 *    │  7    8    3    9  │            │  4    5    0    6  │← -3        │  4    5    0    4  │            ├─╴4╶──╴5╶──╴0╶──╴4╶─┤      +1 →├─╴5╶──╴5╶──╴0╶──╴4╶─┤← -1       ├─╴5╶──╴5╶──╴0╶──╴4╶─┤            │  5    5    0*   4  │
 *    │                    │            │                    │            │                    │            │  │                 │          │  │                 │           │  │              │  │            │                    │
 *    │  2    4    6   10  │            │  0    2    4    8  │← -2        │  0    2    4    6  │            │  0    2    4    6  │          │  0    1    3    5  │← -1       │  0    1    3    5  │            │  0*   1    3    5  │
 *    └────────────────────┘            └────────────────────┘            └────────────────────┘            └──┴─────────────────┘          └──┴─────────────────┘           └──┴──────────────┴──┘            └────────────────────┘
 *            START                             step 1                            step 1                            step 2                          step 3                           step 2                            step 4
 *
 *
 * </pre>
 *
 * <p>The above algorithm is in a generic form. It does not tell how exactly the algorithm should be implemented.
 * For example, step 2 is about finding bipartite maximum matching and minimum vertex cover. Step 4 does not tell
 * how to find the solution. The next section will present a more specific algorithm to address these issues.
 * There are also other methods to address the maximum matching. For details, see {@link net.tp.algo.matching}.
 * The correctness of the algorithm is based on a few theorems:</p>
 * <ul>
 *     <li>When subtracting/adding a value to a row (in step 1, 3), the optimal solution to the new cost matrix does not
 *     change. This can be easily seen by looking at the linear program of the new assignment problem (assuming we add
 *     constant $c$ to the first row of the matrix): minimize $∑↙{i=2..n,j=1..n} c_{ij}x_{ij} + ∑↙{j=1..n} (c_{1j} - c)x_{1j}$.
 *     And $∑↙{i=2..n,j=1..n} c_{ij}x_{ij} + ∑↙{j=1..n} (c_{1j} - c)x_{1j} = ∑↙{i,j} c_{ij}x_{ij} - ∑↙{j} c x_{1j} =
 *     ∑↙{i,j} c_{ij}x_{ij} - c∑↙{j} x_{1j} = ∑↙{i,j} c_{ij}x_{ij} - c$. This is similar to the minimization of the original
 *     problem.</li>
 *     <li>Konig's theorem: for any bipartite graph, the maximum size of a matching = the minimum size of vertex cover.
 *     Step 2 is about finding the minimum vertex cover for those edges with cost = 0. If minimum size of the minimum vertex cover = the number of rows,
 *     then there must exist a maximum matching solution with size = $n$ in step 4.</li>
 * </ul>
 *
 * <p>With the generic form, we can plug different algorithms to find maximum matching and minimum vertex cover. One such method
 * is to find augmenting paths in bipartite graph. See {@link net.tp.algo.matching} for more info about augmenting paths.
 * The method can be extended to solve non-bipartite maximum weighted matching problem using Blossom algorithm.
 * </p>
 *
 * <p>Below is the Hungarian method using just matrix manipulation. The zeros are starred or primed to keep track of
 * maximum matching / minimum vertex cover and to find augmenting path.</p>
 *
 * <ul>
 *     <li>Step 1a: for each row, subtract the minimum value to each of the value.</li>
 *     <li>Step 1b: for each column, subtract the minimum value to each of the value.</li>
 *     <li>Step 2: for each 0, star it if there is no other starred 0 in the same row and column.</li>
 *     <li>Step 3: cover each column containing a starred zero. If the number of covered columns = $n$, TERMINATE with
 *     the solution = {starred zeros}.</li>
 *     <li>Step 4: find a non-covered zero and prime it. If there is a starred zero in the same row, cover the row and uncover the
 *     column containing the starred zero. Repeat this step until there is no non-covered zero left, or a non-covered
 *     zero does not have starred zero in the same row. If the latter case happens, go to step 6.</li>
 *     <li>Step 5: find the minimum entry not crossed out in step 4, add this number to each row/column that is crossed out
 *     (note: add twice for doubly crossed element), then subtract this number to every element. Return to step 4.</li>
 *     <li>Step 6: find a path alternating between prime and star by using this strategy: start with the prime zero,
 *     find a starred zero in the same column. If the starred zero exists, add the starred zero to the path. There must be
 *     another prime zero in the same row with this starred zero, add this prime zero to the path. Repeat this step for the last
 *     found prime zero until until no starred zero is found in the same column with the last found prime zero. The resulting
 *     path is an augmenting path prime-star-...-prime. Unstar all starred zeros and star all prime zeros in this path.
 *     Erase all primes, uncover all rows and columns and go to step 3.</li>
 * </ul>
 *
 * <pre style="overflow:auto">
 *
 *                                                                                     -4        -4                                                                                                                                        +5   +5        +5
 *                                                                                      ↓         ↓                                                                                               ↑                                         ↓    ↓         ↓
 *    ┌─────────────────────────┐          ┌─────────────────────────┐          ┌─────────────────────────┐          ┌─────────────────────────┐          ┌──┬────┬────┬─────────┬──┐          ┌───────┬────┬─────────┬──┐          ┌───────┬────┬─────────┬──┐          ┌───────┬────┬─────────┬──┐          ┌─────────────────────────┐          ┌──┬────┬────┬────┬────┬──┐
 *    │ 90    8    6   12    1  │          │ 89    7    5   11    0  │← -1      │ 89    3    5    7    0  │          │ 89    3    5    7    0* │          │ 89    3    5    7    0* │          │ 89    3    5    7    0* │          │ 84    3    5    2    0* │← -5      │ 84    3    5    2    0* │          │ 84    3    5    2    0* │          │ 84    3    5    2    0* │
 *    │                         │          │                         │          │                         │          │                         │          │  │    │    │         │  │          │       │    │         │  │          │       │    │         │  │          │       │    │         │  │          │                         │          │  │    │    │    │    │  │
 *    │ 15   12    7   90   10  │          │  8    5    0   83    3  │← -7      │  8    1    0   79    3  │          │  8    1    0*  79    3  │          │  8    1    0*  79    3  │          │  8    1    0*  79    3  │          │  3    1    0*  74    3  │← -5      │  3    1    0*  74    3  │          │  3    1    0*  74    3  │          │  3    1    0*  74    3  │
 *    │                         │          │                         │          │                         │          │                         │          │  │    │    │         │  │          │       │    │         │  │          │       │    │         │  │          │       │    │         │  │          │                         │          │  │    │    │    │    │  │
 *    │ 10   90    5   14   90  │          │  5   85    0    9   85  │← -5      │  5   81    0    5   85  │          │  5   81    0    5   85  │          │  5   81    0    5   85  │          │  5   81    0    5   85  │          │  0   81    0    0   85  │← -5      │  0'  81    0    0   85  │          │  0*  81    0    0   85  │          │  0*  81    0    0   85  │
 *    │                         │          │                         │          │                         │          │                         │          │  │    │    │         │  │          │       │    │         │  │          │       │    │         │  │          │  ↓    │    │         │  │          │  ↓                      │          │  │    │    │    │    │  │
 *    │ 12   90   12   16   15  │          │  0   78    0    4    3  │← -12     │  0   74    0    0    3  │          │  0*  74    0    0    3  │          │  0*  74    0    0    3  │         →├─╴0*╶╴74╶──╴0╶──╴0'╶─╴3╶─┤      +5 →├─╴0*╶╴79╶──╴5╶──╴0'╶─╴8╶─┤← -5      ├─╴0*╶→79╶──→5╶──→0'╶─╴8╶─┤          │  0╶─→79╶──→5╶──→0*   8  │          │  0   79    5    0*   8  │
 *    │                         │          │                         │          │                         │          │                         │          │  │    │    │         │  │          │       │    │         │  │          │       │    │         │  │          │       │    │         │  │          │                         │          │  │    │    │    │    │  │
 *    │ 18   17   14   90   13  │          │  5    4    1   77    0  │← -13     │  5    0    1   73    0  │          │  5    0*   1   73    0  │          │  5    0*   1   73    0  │          │  5    0*   1   73    0  │          │  0    0*   1   68    0  │← -5      │  0    0*   1   68    0  │          │  0    0*   1   68    0  │          │  0    0*   1   68    0  │
 *    └─────────────────────────┘          └─────────────────────────┘          └─────────────────────────┘          └─────────────────────────┘          └──┴────┴────┴─────────┴──┘          └───────┴────┴─────────┴──┘          └───────┴────┴─────────┴──┘          └───────┴────┴─────────┴──┘          └─────────────────────────┘          └──┴────┴────┴────┴────┴──┘
 *             START                                step 1                              step 1                               step 2                               step 3                                 step 4                             step 5                               step 4                               step 6                            step 3 - TERMINATE
 * </pre>
 *
 * @author Trung Phan
 *
 */
package net.tp.algo.assignment;
